package main

import "math"

// 41. 缺失的第一个正数
func main() {
	//nums := []int{1, 2, 0}
	nums := []int{1, 2, 3}
	res := firstMissingPositive(nums)

	println(res)
}

func firstMissingPositive2(nums []int) int {
	// 解法 把每个数放到该属于它的下标位置，遍历每个元素，不断置换，直到元素在当前位置了位置
	numLen := len(nums)

	for i := 0; i < numLen; i++ {
		for nums[i] > 0 && nums[i] <= numLen && nums[i] != nums[nums[i]-1] {
			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
		}
	}

	for idx, n := range nums {
		if n != idx+1 {
			return idx + 1
		}
	}

	return numLen + 1
}

func firstMissingPositive(nums []int) int {
	// 解法 用数组 模拟 Map
	// 第一次遍历，元素 不在 0 ～ N 的元素，全部置大， 保障全部大于0
	// 第二次遍历，标记对应下标元素 置为负数
	// 第三次遍历，不是负数的，就是缺失的第一个正数
	numLen := len(nums)
	for i := 0; i < numLen; i++ {
		if nums[i] <= 0 {
			nums[i] = numLen + 1
		}
	}

	for i := 0; i < numLen; i++ {
		absNum := int(math.Abs(float64(nums[i])))
		if absNum <= numLen {
			nums[absNum-1] = -int(math.Abs(float64(nums[absNum-1])))
		}
	}

	for idx, n := range nums {
		if n > 0 {
			return idx + 1
		}
	}

	return numLen + 1
}

//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
//
//请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
//
//示例 1：
//
//输入：nums = [1,2,0]
//输出：3
//示例 2：
//
//输入：nums = [3,4,-1,1]
//输出：2
//示例 3：
//
//输入：nums = [7,8,9,11,12]
//输出：1
//
//
//提示：
//
//1 <= nums.length <= 5 * 105
//-231 <= nums[i] <= 231 - 1
